package org.darcy.controller.portal.puzzle;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

import lombok.Getter;
import lombok.Setter;
import lombok.extern.slf4j.Slf4j;

/**
 * 有25本书，分给5个人，每个人至少一本，且每个人数量都不相同，问：有几种分法？ 答：30
 * 
 */
@Slf4j
@Getter
@Setter
public class DispatchBook {

	public static void main(String[] args) {
		DispatchBook demo = new DispatchBook(100, 13);
		log.debug("问：{}本书分给{}个人，每个人至少一本，且每个人数量都不相同，有几种分法?", demo.getBookCount(), demo.getPeopleCount());
		List<List<Integer>> result = demo.dispatch();
		log.debug("答：{}种", result.size());
	}

	/**
	 * 书本数量
	 */
	private int bookCount;

	/**
	 * 人数量
	 */
	private int peopleCount;
	
	/**
	 * 最少书本数量
	 */
	private int minBookCount;


	/**
	 * bookCount 个数组成 peopleCount 个数的集合
	 */
	private TreeSet<Integer> set = new TreeSet<Integer>();

	/**
	 * 结果集
	 */
	private List<List<Integer>> result = new ArrayList<List<Integer>>();

	public DispatchBook() {

	}

	public DispatchBook(int bookCount, int peopleCount) {
		this.bookCount = bookCount;
		this.peopleCount = peopleCount;
	}

	@SuppressWarnings("unchecked")
	public DispatchBook(TreeSet<Integer> set) {
		this.set = (TreeSet<Integer>) set.clone();
		this.peopleCount = set.size();
		int retBookCount = 0;
		for (int a : set) {
			retBookCount += a;
		}
		this.bookCount = retBookCount;
	}

	/**
	 * 分配算法
	 */
	public List<List<Integer>> dispatch() {
		// 校验合法性
		int min = (this.getPeopleCount() + 1) * this.getPeopleCount() / 2;
		if (min > this.getBookCount()) {
			log.error("输入参数有误，人数={}，书本数={}，最少书本数量应该是：{}", this.getPeopleCount(), this.getBookCount(), min);
			minBookCount = min;
			return null;
		}
		initSet();
		// [1, 2, 3, 4, 15]
		TreeSet<Integer> tmpSet = new TreeSet<Integer>();
		List<List<Integer>> list = getCombination(tmpSet, this.getSet());
		// 输出结果
		// log.debug("计算完毕，所有分配结果如下：");
		// printCombination(list);
		return list;
	}

	/**
	 * 初始化集合：1,2,3,4……
	 */
	private void initSet() {
		for (int i = 1; i < peopleCount; i++) {
			set.add(i);
		}
		set.add(bookCount - peopleCount * (peopleCount - 1) / 2);
	}

	/**
	 * 集合枚举组合数量
	 */
	@SuppressWarnings("unchecked")
	private List<List<Integer>> getCombination(TreeSet<Integer> smallSet, TreeSet<Integer> set) {
		List<List<Integer>> r = new ArrayList<List<Integer>>();
		int count = set.size();
		if (count == 2) {
			int max = set.last();
			int min = set.first();
			while (min < max) {
				List<Integer> data = new ArrayList<Integer>();
				data.addAll(smallSet);
				data.add(min);
				data.add(max);
				min++;
				max--;
				r.add(data);
			}
		} else {
			int max = getMaxFirst(set);
			int min = set.first();
			if (max < min) {
				List<Integer> data = new ArrayList<Integer>();
				data.addAll(smallSet);
				data.addAll(set);
				r.add(data);
				return r;
			}
			for (int i = min; i <= max; i++) {
				TreeSet<Integer> newSmallSet = (TreeSet<Integer>) smallSet.clone();
				TreeSet<Integer> newSet = (TreeSet<Integer>) set.clone();
				dataTransfer(i, newSmallSet, newSet);
				List<List<Integer>> tmpList = getCombination(newSmallSet, newSet);
				r.addAll(tmpList);
			}
		}
		return r;
	}

	/**
	 * smallSet 中增加一个元素data，同时调整set中元素
	 */
	private void dataTransfer(int data, TreeSet<Integer> smallSet, TreeSet<Integer> set) {
		smallSet.add(data);
		int min = smallSet.last() + 1;
		set.clear();
		int retBookCount = 0;// 剩下待分配书本数量
		for (int a : smallSet) {
			retBookCount += a;
		}
		retBookCount = this.getBookCount() - retBookCount;

		for (int i = 0; i < this.getPeopleCount() - smallSet.size(); i++) {
			set.add(min);
			retBookCount -= min;
			min++;
		}
		set.add(set.pollLast() + retBookCount);
	}

	/**
	 * 获取集合中的第一个元素最大可取值
	 */
	private int getMaxFirst(TreeSet<Integer> set) {
		int total = 0;
		int count = set.size();
		for (int a : set) {
			total += a;
		}
		for (int i = 1; i < total; i++) {
			int tmp = i * count + (count - 1) * count / 2;
			if (tmp > total) {
				return i - 1;
			}
		}
		return 0;
	}

	/**
	 * 打印所有组合
	 */
	private void printCombination(List<List<Integer>> result) {
		int index = 1;
		for (List<Integer> a : result) {
			log.info("{}: {}", index++, a);
		}
	}

}
